import { performance } from 'perf_hooks';
import {inOrder} from "../MyClass/Tree.js";

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

//顺序查找
function search(arr,target){
    let count=0
    for(let i=0;i<arr.length;i++){
        count++
        if(arr[i]===target){
            return {count,index:i}
        }
    }
    return {count:arr.length,index:-1}
}


//构建二叉搜索树
function buildSearchTree(array){
    if(array===null || array.length===0){
        return null
    }
    //root:父节点
    //num:要添加的节点的值
    function addNode(root,num){
        //无父节点或者已经添加过这个值，直接跳过
        if(root===null || root.value===num) return;
        //如果要添加的值比父节点大
        if(num > root.value){
            //如果父节点右子节点无值，直接添加
            if(root.right===null){
                root.right=new TreeNode(num)
            }
            //有值，递归调用
            else{
                addNode(root.right,num)
            }
        }
        else{
            //如果父节点左子节点无值，直接添加
            if(root.left===null){
                root.left=new TreeNode(num)
            }
            //有值，递归调用
            else{
                addNode(root.left,num)
            }
        }
    }
    const root=new TreeNode(array[0])
    //1.从1开始循环，因为0是根节点
    for(let i=1;i<array.length;i++){
        addNode(root,array[i])
    }
    return root
}

//使用二叉搜索树搜索
function searchInSearchTree(root,target,count=0){
    if(root===null) return {node:null,count:0}
    count++
    if(root.value===target){
        return {node:root,count:count}
    }
    else if(root.value > target){
        return searchInSearchTree(root.left,target,count)
    }
    else {
        return searchInSearchTree(root.right,target,count)
    }
}


// 查找最大最新小值
function findMin(root){
    while(root && root.left){
        root=root.left
    }
    return root
}
function findMax(root){
    while(root && root.right){
        root=root.right
    }
    return root
}

// 删除二叉搜索树中值为 target 的节点
function deleteNode(root, target) {
    if (root === null) return null; // 空树直接返回 null

    // 目标值小于当前节点值，说明目标在左子树中
    if (target < root.value) {
        root.left = deleteNode(root.left, target);
    }
    // 目标值大于当前节点值，说明目标在右子树中
    else if (target > root.value) {
        root.right = deleteNode(root.right, target);
    }
    // 找到了目标节点，开始删除操作
    else {
        // 情况1：只有右子树或无子节点
        if (root.left === null) {
            return root.right;
        }
        // 情况2：只有左子树
        else if (root.right === null) {
            return root.left;
        }
        // 情况3：左右子树都存在
        else {
            // 找到右子树中最小值（即中序后继）
            const successorValue = findMin(root.right);
            // 用中序后继的值替代当前节点值
            root.value = successorValue;
            // 删除右子树中的中序后继节点:
            root.right = deleteNode(root.right, successorValue);
        }
    }

    return root; // 返回当前（可能被修改的）子树根节点
}

//1.生成10000个乱序数组
let arr=[]
for(let i=0;i<20;i++){
    arr.push(Math.floor(Math.random()*20))
}
let target=arr[Math.floor(Math.random()*20)]
//1.构建二叉搜索树
let treeRoot=buildSearchTree(arr)
//2.中序遍历并打印
// inOrder(treeRoot)
// console.log(arr.join(" "));
// console.log(inOrderList.join(" "));


// === 顺序查找 ===
// const start1 = performance.now();
//
// let { count: count1, index } = search(arr, target);
// const end1 = performance.now();
// console.log(`顺序查找：${count1} 次，下标：${index}，值：${arr[index]}，耗时：${(end1 - start1).toFixed(3)} ms`);
//
// // === 二叉搜索树查找 ===
// const start2 = performance.now();
// let {node,count:count2} = searchInSearchTree(treeRoot, target);
// const end2 = performance.now();
// console.log(`BST 查找：${count2} 次，值：${node?.value}，耗时：${(end2 - start2).toFixed(3)} ms`);
// console.log(findMin(treeRoot));
// console.log(findMax(treeRoot));

// treeRoot=deleteNode(treeRoot,arr[50])
// let {node,count:count2} = searchInSearchTree(treeRoot,arr[21]);
//
// console.log(`BST 查找：${count2} 次，值：${node?.value}`);

//查找前驱节点（中序遍历中的前一个）
function findPreNode(root,target){
    if(root===null) return null
    let current=root
    let preNode=null
    while(current!==null){ //说明没找到
        //1.target在右边，则current有可能是前驱节点,继续往右搜索
        if(target>current.value){
            preNode=current
            current=current.right
        }
        //2. target在左边，当前节点不可能是前驱节点（中序的特点）, 继续往左
        else if(target<current.value){
            current=current.left
        }
        //3. 找到目标节点,前驱节点比目标节点小，但是是目标节点前面一个，因此一定是目标节点右子树中最大的
        else{
            preNode=findMax(current.left)
            //可以提前退出了
            break
        }
    }
    return preNode
}
// console.log(inOrder(treeRoot).join(" "));
// console.log(target);
// console.log(findPreNode(treeRoot,target));


//查找后继节点（中序遍历中的后一个）
function findNextNode(root,target){
    if(root===null) return null
    let current=root
    let nextNode=null
    while(current!==null){ //说明没找到
        //1.节点值小于目标值，不可能是后驱节点
        if(target>current.value){
            current=current.right
        }
        //2. 节点值大于目标值，有可能是后驱节点
        else if(target<current.value){
            nextNode=current
            current=current.left
        }
        //3. 找到目标节点,后驱节点是大于目标节点的值中最小的
        else{
            if(current.right!==null){
                //如果有右子树
                nextNode=findMin(current.right)
            }
            //可以提前退出了
            break
        }
    }
    return nextNode
}
console.log(inOrder(treeRoot).join(" "));
console.log(target);
console.log(findNextNode(treeRoot,target));